/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package uk.co.dupenois.geometry;

import java.util.Comparator;


/**
 *
 * @author mpd209
 */
public class Line implements Cloneable{
    private Coordinate start;
    private Coordinate finish;
    private boolean segment;
    private boolean yNegative;
    private boolean xNegative;
    private boolean vertical;
    private boolean horizontal;
    private double A;
    private double B;
    private double C;
    private double xIntersect;
    private double yIntersect;
    private double slope;
    private double length= -1;
    private double angle = -1;
    public Line(Coordinate start, double angle, double length, boolean segment){
        if(length <= 0)
            throw new IllegalArgumentException("Must have a length");
        this.start = start;
        this.finish = start.getLocationFromMe(angle, length);
        this.segment = segment;
        this.yNegative = (start.getY()>finish.getY());
        this.xNegative = (start.getX()>finish.getX());
        this.length = length;
        this.angle = angle;
        constructLineEquation();
    }
    public Line(Coordinate start, Coordinate finish, boolean segment){
        if(start.equals(finish))
            throw new IllegalArgumentException("Start and finish cannot be the same");
        this.start = start;
        this.finish = finish;
        this.segment = segment;
        this.yNegative = (start.getY()>finish.getY());
        this.xNegative = (start.getX()>finish.getX());
        constructLineEquation();
    }

    private void constructLineEquation(){
        /* Ax + By + C =0
         * Ax1 + By1 = -C = Ax2 + By2
         * A(x1-x2) = B(y2-y1)
         * A^2 + B^2 = 1 :: A^2(y2-y1)^2 + B^2(y2-y1)^2 = (y2-y1)^2
         * A^2(x1-x2)^2 = B^2(y2-y1)^2
         * A^2(y2-y1)^2 +  A^2(x1-x2)^2 = (y2-y1)^2
         * A^2((y2-y1)^2 + (x1-x2)^2) = (y2-y1)^2
         * A = SQRT((y2-y1)^2/((y2-y1)^2 + (x1-x2)^2))
         * B = A(x1-x2)/(y2-y1)
         * C = -1(Ax1 + By1)
        */
        double x1_x2 = this.start.getX()-this.finish.getX();
        double y2_y1 = this.finish.getY()-this.start.getY();
        if(x1_x2==0){
            this.vertical = true;
            this.A = 1;
            this.B = 0;
            this.C = -(this.start.getX());
            this.slope = (isYNegative()?Double.NEGATIVE_INFINITY:Double.POSITIVE_INFINITY);
            this.xIntersect =  this.start.getX();
            this.yIntersect = Double.POSITIVE_INFINITY;
            this.length = Math.abs(finish.getY()-start.getY());
            this.angle = (isYNegative()?3*Math.PI/2:Math.PI/2);
            return;
        }
        if(y2_y1 ==0){
            this.horizontal = true;
            this.A = 0;
            this.B = 1;
            this.C = -1*(this.start.getY());
            this.slope = 0;
            this.xIntersect = Double.POSITIVE_INFINITY;
            this.yIntersect =  this.start.getY();
            this.length = Math.abs(finish.getX()-start.getX());
            this.angle = (isXNegative()?Math.PI/2:0);
            return;
        }
        double x1_x2_2 = Math.pow(this.start.getX()-this.finish.getX(), 2);
        double y2_y1_2 = Math.pow(this.finish.getY()-this.start.getY(), 2);
        this.A = Math.sqrt(y2_y1_2/(y2_y1_2+x1_x2_2));
        this.B = (this.getA()*x1_x2)/(y2_y1);
//        this.C = -(this.A*this.start.getX() + this.B*this.finish.getY());
        this.C = (-1*this.A*this.start.getX() - this.B*this.start.getY());
        this.slope = -getA()/getB();
        this.xIntersect = -getC()/getA();
        this.yIntersect =  -getC()/getB();
        if(this.length < 0){
            if(!isSegment()){
                this.length = Double.POSITIVE_INFINITY;
            }else{
                this.length = start.getDistance(finish);
            }
        }
        if(this.angle < 0){
           this.angle = start.getAngleFromXAxis(finish);
        }
    }

    public double length(){
        return this.length;
    }

    public boolean isCoordinateRightOfLine(Coordinate coord){
       return (coordinateInRelationToLine(coord)<0);
    }
    public boolean isCoordinateLeftOfLine(Coordinate coord){
       return (coordinateInRelationToLine(coord)>0);
    }
    public boolean isCoordinateOnLine(Coordinate coord){
       return (coordinateInRelationToLine(coord)==0);
    }
    /**
     * determine  x =   (y0-y1)(x2-x1)/(y2-y1) + x1<br/>
     *  <ul>
     *   <li>if x &lt; x0 then point is right of line</li>
     *   <li>if x = x0 then point is on line</li>
     *   <li>if x gt; x0 then point is left of line</li>
     * </ul><br/>
     *  So we return:
     *  <ul>
     *   <li>-1 if x &lt; 0 (Right(</li>
     *   <li>0 if x = 0 (On)</li>
     *   <li>1 if x &gt; 0 (Left)</li>
     * </ul>
     * @param coord Coordinate to check
     * @return position of the coordinate relative to line
     */
    public int coordinateInRelationToLine(Coordinate coord){
        /*determine  x =   (y0-y1)(x2-x1)/(y2-y1) + x1
            if x < x0 then point is right of line
            if x= x0 then point is on line
            if x > x0 then point is left of line
         */
         /*
           For three points (x1,y1), (x2,y2) and (x3,y3),
          simply compute the direction of the cross product
          of the two vectors defined by points (x1,y1), (x2,y2) and (x1,y1), (x3,y3),
          characterized by the sign of the expression (x2 − x1)(y3 − y1) − (y2 − y1)(x3 − x1).
          If the result is 0, the points are collinear; if it is positive,
          the three points constitute a "left turn", otherwise a "right turn"
          */

        double x1 = this.start.getX();
        double y1 = this.start.getY();
        double x2 = this.finish.getX();
        double y2 = this.finish.getY();
        double x3 = coord.getX();
        double y3 = coord.getY();

        double val = ((x2 - x1)*(y3 - y1)) - ((y2 - y1)*(x3 - x1));
//        double val = (this.finish.getX()-this.start.getX()*(coord.getY()-this.start.getY()))-
//        (this.finish.getY()-this.start.getY())*(coord.getX()-this.start.getX());
        if(val<0) return -1;
        if(val==0) return 0;
        return 1;
    }
    private double getDirectedAngleFromMeTo(Line other, boolean clockwise){
        if(this.isParallel(other)){
//            System.out.println("This ("+this.getStart()+"->"+this.getFinish()+") is parallel to ("+other.getStart()+"->"+other.getFinish()+")");
            return Math.PI;
        }
//        System.out.println("Both Segments: "+(this.isSegment()&&other.isSegment()));
        if(this.isSegment()&&other.isSegment())
            return this.getAngleDirectedFromSegmentMeToSegment(other, clockwise);
        //If not both segments ignore segmentation
        Coordinate intersection = coincides(other, true);
        /*
          * Okay the issue is which points to choose
          *  As this effects which angle we get
             \  O /     \                           /         \   |
              a  i       i                         i           \  a
               \/       O \                     O /             i |
               /\     --a-----b----     ----a-------b-----       \|O
              j  b          \                   /                 |\
             /    \          j                 j                  b j
                              \               /                   |  \
        
             \    /     \                           /         \   |
              i  a       a                         a           \ Oi
               \/ O       \ O                     /  O          a |
               /\     --i-----j----     ----i-------j-----       \|
              b  j          \                   /                 |\
             /    \          b                 b                  j b
                              \               /                   |  \
        
         * a->b = this
         * i->j = otherLine
         *
         * To make it easy take a point on this line that's before intersection
         * on the x axis, if the line's vertical make it higher than the intersection
         * on the y axis
         *
        */
        Coordinate pointFromThis;
        if(!this.isVertical()){
            pointFromThis =  this.getCoordByX(intersection.getX()-1, true);
        }else{
            pointFromThis = this.getCoordByY(intersection.getY()+1, true);
        }
        /*
         * Having this we can get two possible coordinates from other,
         * one before intersection on the x axis and one after,
         * if the line's vertical make it higher and lower than the intersection
         * on the y axis
        */
        Coordinate pointFromOther1;
        Coordinate pointFromOther2;
        if(!other.isVertical()){
            pointFromOther1 =  other.getCoordByX(intersection.getX()-1, true);
            pointFromOther2 =  other.getCoordByX(intersection.getX()+1, true);
        }else{
            pointFromOther1 =  other.getCoordByY(intersection.getY()-1, true);
            pointFromOther2 =  other.getCoordByY(intersection.getY()+1, true);
        }
        /*
         * Now use whichever of these is on the left of pointFromThis to intersection
         * or right if anticlockwise
        */
        Line pointFromThisToIntersection = new Line(pointFromThis, intersection, true);
        if(clockwise){
            if(pointFromThisToIntersection.isCoordinateLeftOfLine(pointFromOther1)){
                return intersection.getAngle(pointFromThis, pointFromOther1);
            }else{
                return intersection.getAngle(pointFromThis, pointFromOther2);
            }
        }else{
            if(pointFromThisToIntersection.isCoordinateRightOfLine(pointFromOther1)){
                return intersection.getAngle(pointFromThis, pointFromOther1);
            }else{
                return intersection.getAngle(pointFromThis, pointFromOther2);
            }
        }


    }
    public double getAngleAntiClockwiseFromMeTo(Line other){
        return this.getDirectedAngleFromMeTo(other, false);

    }
    public double getAngleClockwiseFromMeTo(Line other){
        return this.getDirectedAngleFromMeTo(other, true);

    }
 
    
    private double getAngleDirectedFromSegmentMeToSegment(Line other, boolean clockwise){
        if(this.isParallel(other)) {
//            System.out.println("This ("+this.getStart()+"->"+this.getFinish()+") is parallel to ("+other.getStart()+"->"+other.getFinish()+")");
            return Math.PI;
        }
        Coordinate intersection = coincides(other, true);
//        System.out.println("Intersection = "+intersection);
        /*
              \        ----a---\ O                 /
               i                \                 i
              O \                i            O  /
         ----a---\                \      ---a---/

              \        ----i---\
               a              O \
                \                a
         ----i---\ O              \


         * a = this
         * i = otherLine
         * If they don't coincide on segment doesn't matter which point from
         * start or finish we use, otherwise we want whichever point is not
         * equal to the intersection
         */
        Coordinate pointFromThis;
        Coordinate pointFromOther;
        if(this.getStart().equalsCheck(intersection)){
            pointFromThis = this.getFinish();
        }else{
            pointFromThis = this.getStart();
        }
        if(other.getStart().equalsCheck(intersection)){
            pointFromOther = other.getFinish();
        }else{
            pointFromOther = other.getStart();
        }
        Line pointFromThisToIntersection = new Line(pointFromThis, intersection, true);
//        System.out.println("Using "+pointFromThis+" as pointFromThis");
//        System.out.println("Using "+pointFromOther+" as pointFromOther");
        /*
         * So if pointfromother is right of thisToIntersectionLine a
         * we want to use 2*math.pi -angle (other way round for anticlockwise)
        */
        

        //If point from other is left of this line we use the inner angle
        //If not we use the outer (2pi-angle) (2pi = 360deg), right if not clockwise
        double myAngle = intersection.getAngle(pointFromThis, pointFromOther);
//        System.out.println("original angle: "+myAngle+" degrees "+Math.toDegrees(myAngle));

        if(clockwise){
            if(pointFromThisToIntersection.isCoordinateLeftOfLine(pointFromOther)){
//                System.out.println(pointFromOther+" is LEFT of : "+
//                        pointFromThisToIntersection.getStart()+"->"+pointFromThisToIntersection.getFinish());
                return myAngle;
            }else{
//                System.out.println(pointFromOther+" is RIGHT of : "+
//                        pointFromThisToIntersection.getStart()+"->"+pointFromThisToIntersection.getFinish());
                return (2*Math.PI)-myAngle;
            }
        }else{
            if(pointFromThisToIntersection.isCoordinateRightOfLine(pointFromOther)){
//                System.out.println(pointFromOther+" is RIGHT of : "+
//                        pointFromThisToIntersection.getStart()+"->"+pointFromThisToIntersection.getFinish());
                return myAngle;
            }else{
//                System.out.println(pointFromOther+" is LEFT of : "+
//                        pointFromThisToIntersection.getStart()+"->"+pointFromThisToIntersection.getFinish());
                return (2*Math.PI)-myAngle;
            }
        }

    }


    

    

    /**
     *
     * @param line
     * @return smallest positive angle between two lines
     */
    public double getAngleTo(Line line){
        if(this.isParallel(line)) return Math.PI;

        double clockwise = getAngleClockwiseFromMeTo(line);
        double antiClockwise = getAngleAntiClockwiseFromMeTo(line);

        if(clockwise<antiClockwise) return clockwise;
        return antiClockwise;

    }

    public Coordinate getMidpoint(){
        double midX = (this.start.getX()+this.finish.getX())/2;
        double midY = (this.start.getY()+this.finish.getY())/2;
        return new Coordinate(midX, midY);
    }
    public Line getPerpendicular(Coordinate intersection){
        Coordinate perpendicularFinish;
        if(this.horizontal){
            if(this.segment){
                perpendicularFinish = new Coordinate(intersection.getX(), intersection.getY()+this.length);
            }else{
                perpendicularFinish = new Coordinate(intersection.getX(), intersection.getY()+1);
            }
        }else if(this.vertical){
            if(this.segment){
                perpendicularFinish = new Coordinate(intersection.getX()+this.length, intersection.getY());
            }else{
                perpendicularFinish = new Coordinate(intersection.getX()+1, intersection.getY());
            }
        }else{
            double perpendicularSlope = -1/this.slope;
            double perpendicularC = intersection.getY()-(intersection.getX()*perpendicularSlope);
            double y2 = (intersection.getX()+1)*perpendicularSlope + perpendicularC;
            perpendicularFinish = new Coordinate(intersection.getX()+1, y2);
        }
        return new Line(intersection, perpendicularFinish, this.segment);
    }

    public Coordinate getCoordFrom(Coordinate from, double distance){
//        System.out.println("Start "+from.toString()+" on segment "+start.toString()+
//                " to "+finish.toString()+": "+isOnLineSegment(from)+
//                " xNegative: "+isXNegative()+" yNegative: "+isYNegative());
        if(isSegment()&&!isOnLineSegment(from)) return null;
        Coordinate loc = from.getLocationFromMe(this.angle, distance);
//        System.out.println("Next Coord: "+loc.toString()+" on segment: "+isOnLineSegment(loc));
        if(isSegment()&&!isOnLineSegment(loc)) return null;
        return loc;
    }
    public Coordinate getCoordByX(double y){
        return getCoordByY(y, false);
    }
    public Coordinate getCoordByX(double x, boolean ignoreSegment){
        if(this.isVertical()){
            return new Coordinate(x, this.getC());
        }
        /* Ax + By + C = 0
         * y = (-Ax -C)/B
        */
        Coordinate coord = new Coordinate(x, (-this.getA()*x - this.getC())/this.getB());
        if(!ignoreSegment&&isSegment()&&!isOnLineSegment(coord)) return null;
        return coord;
    }
    public Coordinate getCoordByY(double y){
        return getCoordByY(y, false);
    }
    public Coordinate getCoordByY(double y, boolean ignoreSegment){
         
        if(this.isHorizontal()){
            return new Coordinate(this.getC(), y);
        }
        /* Ax + By + C = 0
         * x = (-By -C)/A
        */
        Coordinate coord = new Coordinate((-this.getB()*y - this.getC())/this.getA(), y);
//        System.out.println("A: "+this.getA());
//        System.out.println("x: "+(((-1*this.getB())*y - this.getC())/this.getA()));
//        System.out.println("coord: "+coord);
        
        if(!ignoreSegment&&isSegment()&&!isOnLineSegment(coord)) return null;
        return coord;
    }
    public boolean isParallel(Line line){
         if(line.isHorizontal() && this.isHorizontal()) return true;
         if(line.isVertical() && this.isVertical()) return true;
         //Account for rounding errors
         double slopeDiff = line.getSlope()-this.getSlope();
         if(Math.abs(slopeDiff)<0.0000001){
             return true;
         }
         return false;
    }
    public Coordinate coincides(Line line){
        return coincides(line, false);
    }
    public Coordinate coincides(Line line, boolean ignoreSegment){
        Coordinate coincides = null;
        if(isParallel(line)) return null;
        if(!this.isHorizontal()){
            /* Ax + By + C = 0
             * A1x + B1y + C1 = 0
             * A2x + B2y + C2 = 0
             * x = (-B1y -C1)/A1
             * A2((-B1y -C1)/A1) + B2y + C2 = 0
             * y = (A2C1-A1C2)/(A1B2-A2B1)
             */
            double A2C1 = line.getA()*this.C;
            double A1C2 = this.A*line.getC();
            double A1B2 = this.A*line.getB();
            double A2B1 = line.getA()*this.B;
            double y = (A2C1-A1C2)/(A1B2-A2B1);
            coincides = this.getCoordByY(y, ignoreSegment);
        }else{
             /* Ax + By + C = 0
             * A1x + B1y + C1 = 0
             * A2x + B2y + C2 = 0
             * y = (-A1x -C1)/B1
             * A2x + B2((-A1x -C1)/B1) + C2 = 0
             * x = (B2C1 - B1C2)/(A2B1-A1B2)
             */

//             System.out.println("Line: "+line.toString());
//             System.out.println("this: "+this.toString());
//             System.out.println("Line gradient: "+line.getSlope());
//             System.out.println("Line y-intersect: "+line.getYIntersect());
             double B2C1 = line.getB()*this.C;
//             System.out.println("B2C1: "+B2C1);

             double B1C2 = this.getB()*line.getC();
//             System.out.println("B1C2: "+B1C2);
             double A2B1 = line.getA()*this.B;
//             System.out.println("A2B1: "+A2B1);
             double A1B2 = this.A*line.getB();
//             System.out.println("A1B2: "+A1B2);
             double x = (B2C1-B1C2)/(A2B1-A1B2);
//             System.out.println("X: "+x);
             coincides = this.getCoordByX(x, ignoreSegment);
        }
        if(!ignoreSegment&&
                ((isSegment() && !isOnLineSegment(coincides))||
                (line.isSegment() && !line.isOnLineSegment(coincides))))
                return null;
        return coincides;
    }

    public boolean isOnLine(Coordinate coord){
        Coordinate onLine;
        if(!this.isVertical()){
            onLine = this.getCoordByX(coord.getX(), true);
        }else{
            onLine = this.getCoordByY(coord.getY(), true);
        }
        return onLine.equalsCheck(coord);
    }

    public boolean isOnLineSegment(Coordinate point){
        if(!isSegment()) return true;
        if(start.equals(finish)) return false;
        if(start.getX() == finish.getX()){
            if(isYNegative()){
                return (finish.getY()<=point.getY()&&point.getY()<=start.getY());
            }else{
                return (start.getY()<=point.getY()&&point.getY()<=finish.getY());
            }
        }else if(start.getY() == finish.getY()){
            if(isXNegative()){
                return (finish.getX()<=point.getX()&&point.getX()<=start.getX());
            }else{
                return (start.getX()<=point.getX()&&point.getX()<=finish.getX());
            }
        }else{
//            System.out.println("Start is "+(start==null?"":"NOT ")+"null");
//            System.out.println("Finish is "+(finish==null?"":"NOT ")+"null");
//            System.out.println("Point is "+(point==null?"":"NOT ")+"null");
            boolean between_y = false;
            boolean between_x = false;
            if(isYNegative()){
                between_y = (finish.getY()<=point.getY()&&point.getY()<=start.getY());
            }else{
                between_y = (start.getY()<=point.getY()&&point.getY()<=finish.getY());
            }
            if(isXNegative()){
                between_x = (finish.getX()<=point.getX()&&point.getX()<=start.getX());
            }else{
                between_x = (start.getX()<=point.getX()&&point.getX()<=finish.getX());
            }
            return(between_x&&between_y);
        }
    }

    /**
     * @return the start
     */
    public Coordinate getStart() {
        return start;
    }

    public Coordinate getLeftCoordinate(){
        if(start.getX()<=finish.getX()) return start;
        return finish;
    }
    public Coordinate getRightCoordinate(){
        if(finish.getX()>=start.getX()) return finish;
        return start;
    }
    /**
     * @return the finish
     */
    public Coordinate getFinish() {
        return finish;
    }

    /**
     * @return the segement
     */
    public boolean isSegment() {
        return segment;
    }

    /**
     * @return the yNegative
     */
    public boolean isYNegative() {
        return yNegative;
    }

    /**
     * @return the xNegative
     */
    public boolean isXNegative() {
        return xNegative;
    }

    /**
     * @return the xIntersect
     */
    public double getXIntersect() {
        return xIntersect;
    }

    /**
     * @return the yIntersect
     */
    public double getYIntersect() {
        return yIntersect;
    }

    /**
     * @return the slope
     */
    public double getSlope() {
        return slope;
    }

    @Override
    public String toString(){
        return this.getA()+"x + "+this.getB()+"y + "+this.getC()+" = 0";
    }

    /**
     * @return the vertical
     */
    public boolean isVertical() {
        return vertical;
    }

    /**
     * @return the horizontal
     */
    public boolean isHorizontal() {
        return horizontal;
    }

    /**
     * @return the A
     */
    public double getA() {
        return A;
    }

    /**
     * @return the B
     */
    public double getB() {
        return B;
    }

    /**
     * @return the C
     */
    public double getC() {
        return C;
    }

    /**
     * @return the angle
     */
    public double getAngleFromX() {
        return angle;
    }

    @Override
    public boolean equals(Object other){
        if(other==this)return true;
        if(!(other instanceof Line))return true;
        Line line = (Line) other;
        return (line.hashCode()==this.hashCode());
    }

    @Override
    public int hashCode() {
        int hash = 5;
        if(this.isSegment()){
            hash = 31 * hash + (this.start != null ? this.start.hashCode() : 0);
            hash = 31 * hash + (this.finish != null ? this.finish.hashCode() : 0);
        }
        hash = 31 * hash + (int) (Double.doubleToLongBits(this.A) ^ (Double.doubleToLongBits(this.A) >>> 32));
        hash = 31 * hash + (int) (Double.doubleToLongBits(this.B) ^ (Double.doubleToLongBits(this.B) >>> 32));
        hash = 31 * hash + (int) (Double.doubleToLongBits(this.C) ^ (Double.doubleToLongBits(this.C) >>> 32));
        return hash;
    }

    @Override
    public Line clone(){
        return new Line(this.start, this.finish, this.segment);
    }


}
